\begin{frame}
\frametitle{Two-Dimensional Sgraffito Automata I}
\begin{define}[(2SA)2DSA~\cite{pruuvsa2013comparing}~\cite{pruuvsa2013new}~\cite{pruvsa2012new}~\cite{PrusaMraz2012}]
A $[$non-$]$deterministic two-dimensional sgraffito automaton is a 7-tuple
$M~=~(Z,~\Sigma,~\Gamma,~\delta,~z_0,~E,~\mu)$, where
\begin{itemize}
	\item Z is a finite non-empty set of states
	\item $\Sigma$ is a finite set of input symbols
	\item $\Gamma$ is working alphabet containing $\Sigma$
	\item $z_0~\in~Z$ is the initial state
	\item E~$\subseteq$~Z is the set of accepting states
\end{itemize}
\end{define}
\end{frame}

\begin{frame}
\frametitle{Two-Dimensional Sgraffito Automata II}
\begin{define}[(2SA)2DSA~\cite{pruuvsa2013comparing}~\cite{pruuvsa2013new}~\cite{pruvsa2012new}~\cite{PrusaMraz2012}]
\begin{itemize}
	\item
	$[\delta:~(Z~\setminus~E)~\times~(\Gamma~\cup~\mathcal{S})~\rightarrow~2^{Z~\times~(\Gamma~\cup~\mathcal{S})~\times~\mathcal{H}}]$
	$\delta:~(Z~\setminus~E)~\times~(\Gamma~\cup~\mathcal{S})~\rightarrow~Z~\times~(\Gamma~\cup~\mathcal{S})~\times~\mathcal{H}$
	is the control function, where $\mathcal{H}~=~\{R,~L,~D,~U,~N\}$ is a set of
	directions and $\mathcal{S}~=~\{\vdash,~\dashv,~\top,~\bot,~\#\}$ is a set of
	border symbols with $\Gamma~\cap~\mathcal{S}~=~\emptyset$
	\item $\mu:~\Gamma~\rightarrow~\mathbb{N}$ is a weight function
\end{itemize}
\end{define}
$M$ is bounded, that is, whenever it scans a symbol from $\mathcal{S}$, then it
immediately moves to the nearest field of picture $p\in\Sigma^{*,*}$ without
changing this symbol. 

$M$ is weight-reducing, that is, for all $z, z' \in Z, d \in \mathcal{H}$,
and $a, a'\in \Gamma$, if $(z', a', d) \in \delta(z, a)$, then $\mu(a') <
\mu(a)$.
\end{frame}

\begin{frame}
\frametitle{Example I}
Let $L$ (Lemma 6.4 in~\cite{pruvsa2012new}) be a picture language over
$\Sigma = \{0,1,2\}$ consisting of all pictures of the form $P = Q_1\obar C\obar Q_2$, where 
\begin{itemize}
  \item $Q_1$ and $Q_2$ are non-empty square pictures over $\{0, 1\}$, and
  \item $C$ is a column over $\{2\}$.
\end{itemize}
It is easy to see that each $P\in L$ is of size $(n, 2n + 1)$ for some $n\geq
1$.
\end{frame}

\begin{frame}
\frametitle{Example II}
Each computation of $M$ consists of two phases (Proof of lemma 6.4
in~\cite{pruvsa2012new}). In the first checks $M$ if the size is $(n, 2n + 1)$ and whether the middle column contains only 2'. In
the second phase checks $M$ if all occurrences of 2's are located only in single column. That implies that $L(M) = L$.
Here we can see the computation phases.
\includegraphics[width=\textwidth]{img/example_sgraffito_automaton.png}
\end{frame}

\begin{frame}
\frametitle{Example III}
\footnotesize 
\begin{example}
$M~=~(\{z_0, \ldots, z_{11}, z_e\}, \{0, 1, 2\}, \{0, 1, 2, x_1, x_2, x_3, x_4,
x_5\}, \delta, z_0, \{z_e\}, \mu)$ \\
$\mu(0) > \mu(1) > \mu(2) > \mu(x_1) > \mu(x_2) > \mu(x_3) > \mu(x_4) > \mu(x_5) = 0$
\centering
\resizebox{10cm}{!} {
\begin{tabular}{c|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}}
$\delta$ & 0, 1 & 2 & $\vdash$ & $\top$ & $\dashv$ & $\bot$ & $x_i(i\in\{1,2,3,4\})$ \tabularnewline
\hline
$z_0$ & ($z_1$, $R$, $x_1$) & - & - & - & - & - & - \tabularnewline
\hline
$z_1$ & ($z_0$, $D$, $x_1$) & ($z_2$, $U$, $x_1$) & - & - & - & - & - \tabularnewline
\hline
$z_2$ & - & ($z_2$, $U$, $x_1$) & - & ($z_3$, $D$, $\top$) & - & - & - \tabularnewline
\hline
$z_3$ & - & - & - & - & - & - & ($z_4$, $R$, $x_{i+1}$) \tabularnewline
\hline
$z_4$ & ($z_5$, $R$, $x_1$) & - & - & - & - & - & - \tabularnewline
\hline
$z_5$ & ($z_4$, $D$, $x_1$) & - & - & - & ($z_6$, $L$, $\dashv$) & - & - \tabularnewline
\hline
$z_6$ & - & - & - & - & - & - & ($z_7$, $D$, $x_{i+1}$) \tabularnewline
\hline
$z_7$ & - & - & - & - & - & ($z_8$, $U$, $\bot$) & - \tabularnewline
\hline
$z_8$ & ($z_8$, $U$, $x_1$) & - & - & ($z_{9}$, $D$, $\top$) & - & - & ($z_8$, $U$, $x_{i+1}$) \tabularnewline
\hline
$z_{9}$ & - & - & - & - & - & - & ($z_{10}$, $L$, $x_{i+1}$) \tabularnewline
\hline
$z_{10}$ & ($z_{10}$, $D$, $x_1$) & - & ($z_e$, $R$, $\vdash$) & - & - & ($z_{11}$, $U$, $\bot$) & ($z_{10}$, $D$, $x_{i+1}$) \tabularnewline
\hline
$z_{11}$ & - & - & - & - & - & - & ($z_8$, $L$, $x_{i+1}$)
\end{tabular}
}
\end{example}
\end{frame}

\begin{frame}
\frametitle{Closure Properties}
\begin{thm}[Theorem 6.1, 6.2, 6.6~\cite{pruvsa2012new}, Theorem
2, 3, 5~\cite{PrusaMraz2012}]
$\mathcal{L}(2SA)$ is closed under projection, concatenation, union,
intersection, rotation and mirroring.\\
$\mathcal{L}(2SA)$ is not closed under complement.
\end{thm}
\begin{thm}[Theorem 6.1, 6.3, 6.7, 6.8~\cite{pruvsa2012new}, Theorem
2, 4, 5, 6~\cite{PrusaMraz2012}] $\mathcal{L}(2DSA)$ is closed under complement,
union, intersection, rotation and mirroring.\\
$\mathcal{L}(2DSA)$ is not closed under concatenation and projection.
\end{thm}
\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Language hierarchy}
\begin{thm}[Theorem 4.6~\cite{pruvsa2012new}, Theorem 7~\cite{PrusaMraz2012}]
$\mathcal{L}(4FA)\subset\mathcal{L}(2DSA)$
\end{thm}
\begin{thm}[Theorem 7.1~\cite{pruvsa2012new}, Theorem 8~\cite{PrusaMraz2012}]
$REC\subset\mathcal{L}(2SA)$ \\
$DREC\subset\mathcal{L}(2DSA)$
\end{thm}
\begin{thm}[Theorem 7.4~\cite{pruvsa2012new}, Theorem 9~\cite{PrusaMraz2012}]
Classes $REC$ and $\mathcal{L}(2DSA)$ are incomparable.
\end{thm}
\begin{thm}[Corollary 1~\cite{pruuvsa2013comparing}]
$\mathcal{L}(DMA(1))\subset\mathcal{L}(2DSA)$
\end{thm}
\begin{thm}[Theorem 2~\cite{pruuvsa2013comparing}]
$\mathcal{L}(MA(1))\not\subset\mathcal{L}(2SA)$
\end{thm}
\begin{thm}[Theorem 2~\cite{pruuvsa2013new}]
$\mathcal{L}(4AFA)\subset\mathcal{L}(2DSA)$
\end{thm}
\begin{thm}[Theorem 3~\cite{pruuvsa2013new}]
$SDREC\subset\mathcal{L}(2DSA)$
\end{thm}
\end{frame}